package binarytree

type TreeNode struct{
	Val int
	Left,Right *TreeNode
}

// 找满足要求的路径
func pathSum(root *TreeNode, targetSum int) [][]int {
	if root == nil {
		return nil
	}
	var dfs func(node *TreeNode, path *[]int, pathSum int, res *[][]int)
	// 遍历整棵树 不要返回值
	dfs = func(node *TreeNode, path *[]int, pathSum int, res *[][]int) {
		// 先序遍历
		*path = append(*path, node.Val)
		pathSum += node.Val
		// 终止条件
		// 遇到叶子节点
		if node.Left == nil && node.Right == nil {
			// 判断是否满足要求
			if pathSum == targetSum {
				// 满足要求，加入res
				// 放入path副本 因为底层path只有一个
				var pathCpy []int
				for i:=0;i<len(*path);i++{
					pathCpy = append(pathCpy, (*path)[i])
				}
				*res = append(*res, pathCpy)
				// 找出所有的路径
			}
		}

		// 单层逻辑  前序遍历
		if node.Left != nil {
			// 访问左节点
			dfs(node.Left, path, pathSum, res)
		}
		if node.Right != nil {
			dfs(node.Right, path, pathSum, res)
		}
		// 当前节点遍历完 出栈
		*path = (*path)[:len(*path)-1]
	}
	var res [][]int
	dfs(root,&[]int{},0,&res)
	return res
}